昨天猶豫了很久要再堅持幾天 DP，還是開啟圖論大門。到了今天依舊有點糾結，明明圖論的標題都打好了，最後想想還是再消滅一個 DP 的子類吧。

老實說跟 bit 相關的東西真的超級不想碰，很久以前偶爾打每日題的時候，就有一次被 bitmask dp 搞到頭昏腦脹，從此看了都想繞路走退避三舍 ヾ(ﾟ皿ﾟＯ＝Ｏﾟ皿ﾟ)ノ

要解 bitmask 題目有幾個前置觀念：

1. 二進位字串的運用
   • 可以用二進位數字來代表狀態
   • 例如有 1-5 五件物品，可以用五位數的 bit number 來表示選取情形，像是 10100 表示選擇了第三和第五件物品，00111 表示選擇了第一到三件物品，bit 表示的順序是前往後還是後往前（第一位數代表第一個還是最後一個物品）由個人定義
2. 判斷第 n 位是否為 1
   • 假設由右到左來做標示，00001 表示第一件物品，00010 表示第二件
   • 判斷第 n 位數的方法：把數字平移後做 AND operation。例如 a 是一個二進位數字，(a >> (n-1)) & 1 會先把 a 往右平移 n-1 位，因此原本的第 n 位平移後到了最末位，再用 AND 就可以得出結果
3. 把第 n 位的數字拔掉
   • 用 1 << (n-1) 可以得到除了第 n 位為 1，其他位都為 0 的數字
   • ~a 會得到把 a 所有位數全部做相反操作的數字，例如 00110 會變成 11001
   • 所以用 b & (~(1 << (n-1))) 可以得到把 b 的第 n 位拔掉變成 0 的數字

有了這兩個前置概念，接著就可以來寫 dp table。第一個維度記的是 array 長度（會從長度為 1 推到長度為 n），第二個維度則是用二進位數字表示目前狀態，因此至少需要 2^n 個位置。而 dp table 裡面的數字則表示「在目前長度為 i 的 array，且 current state (item set) 為 j 的情況下總共的方案數」，因此會去推敲上一層可能的情況，判斷是否有機會從上個狀態轉移過來。

class Solution:
    def countArrangement(self, n: int) -> int:
        mask = 1 << n
        f = [[0] * mask for _ in range(n + 1)]
        f[0][0] = 1
        
        for i in range(1, n + 1):
            for state in range(mask):
                for k in range(1, n + 1):
                    if (state >> (k - 1)) & 1 == 0:  # case1
                        continue
                    if k % i != 0 and i % k != 0:
                        continue
                    f[i][state] += f[i - 1][state & (~(1 << (k - 1)))]

        return f[n][mask - 1]

其實就是走 dp 的轉移矩陣，因為最外層是當次新加入的數字，所以在內層中，會去看這個位置（像是第四個位置）能不能放入某個數（例如算 4%5 和 5%4），如果可以的話，就去找「拔掉這個數字後上一次的狀態」然後加回來。

• Resource

  • 算法通关手册（LeetCode）- 01. 状态压缩 DP 知识

• bitmask dp

  • 526. Beautiful Arrangement

Total Count: 19